import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/31 21:30
 * @description 思路：搜索回溯，搜素前先将数字排序，访问相同的元素直接跳过
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 1, 1, 2};
        solution.permuteUnique(nums);
    }

    boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> perm = new ArrayList<>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans , 0, perm);
        return ans;
    }
    public void backtrack(int[] nums, List<List<Integer>> ans, int idx,  List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<>(perm));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (vis[i] || (i > 0 && nums[i] == nums[i-1] && !vis[i-1])) {
                // 保证在填第 idx 个数的时候重复数字只会被填入一次即可 !vis[i-1] 前面相同的要优先访问了，才能接下来访问i
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}
